package algorithm.niuke;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * 反转链表
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-05-07
 */
public class LinkedListReverse {

    public static void main(String[] args) {

        ListNode node = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(3);
        node.setNext(node1);
        node1.setNext(node2);

        System.out.println("实现2");
        ArrayList<Integer> result = reverse1(node);
        System.out.println(result);

        System.out.println("实现1");
        ArrayList<Integer> list = reverse(node);
        System.out.println(list);


    }

    /**
     * 实现1：会破坏原先链表
     * 根据传入的链表，按链表从尾到头的顺序返回
     * 思路：借助辅助链表实现反转
     * @param node 链表
     * @return 返回反转之后的链表
     */
    private static ArrayList<Integer> reverse(ListNode node) {

        ArrayList<Integer> reverseList = new ArrayList<>(10);

        if (node == null){
            return null;
        }
        if (node.getNext() == null){
            reverseList.add(node.getVal());
            return reverseList;
        }

        ListNode reverseHead = new ListNode(0);
        ListNode curNode = node;
        ListNode curNextNode;
        while (curNode != null){
            curNextNode = curNode.getNext();
            curNode.setNext(reverseHead.getNext());
            reverseHead.setNext(curNode);
            curNode = curNextNode;
        }

        while (reverseHead.getNext() != null){
            reverseList.add(reverseHead.getNext().getVal());
            reverseHead = reverseHead.getNext();
        }

        return reverseList;
    }

    /**
     * 实现2：
     * 思路：
     * 借助JDK提供的LinkedList充当栈实现
     *
     * @param node 链表
     * @return 返回反转之后的链表
     */
    private static ArrayList<Integer> reverse1(ListNode node){

        LinkedList<Integer> stack = new LinkedList<>();
        ArrayList<Integer> result = new ArrayList<>(10);

        while (node != null){
            stack.push(node.getVal());
            node = node.getNext();
        }
        while (!stack.isEmpty()){
            result.add(stack.pop());
        }

        return result;
    }
}

/**
 * 链表节点
 */
class ListNode {

    private int val;
    private ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public ListNode getNext() {
        return next;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }
}
